#include <bits/stdc++.h> 
using namespace std;

//要求：时间log(n)

//1.找旋转点
// class Solution {
// public:
//     int findK(vector<int>& nums){
//         int left = 0; int right = nums.size()-1;
//         if(nums[left] < nums[right]) return 0;  //升序处理
//         int mid;
//         while(left < right){
//             mid = (left + right) >> 1;
//             if(nums[mid] >= nums[left]) left = mid;
//             else right = mid;
//             if(right - left == 1) break;
//         }
//         int ans = nums[left]<nums[right] ? left:right; 
//         return ans;
//     }
//     int search(vector<int>& nums, int target) {
//         int k = findK(nums);
//         int len = nums.size();
//         int left = 0; int right = nums.size()-1;
//         int mid;
//         while(left < right){
//             mid = (left + right) >> 1;
//             if(nums[(mid+k)%len] < target) left = mid + 1;
//             else right = mid;
//         }
        
//         if(nums[(left+k)%len] != target) return -1;
//         else return (left+k)%len;
//     }
// };

//2.分治:一分为二，其中一个一定有序，另一个可能有序可能无序。
//如果target在有序部分，则使用二分；否则重复

//二分core:
//  left or right 是否移位看是否验证mid，验证的形式有①if(nums[mid] == target), target<=nums[mid]等
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0; int right = nums.size()-1;
        while(left <= right){
            int mid = (left+right) >> 1;
            if(nums[mid] == target) return mid;
            if(nums[left] <= nums[mid]){//如果左半有序(必须加等号)
                if(nums[left]<=target && target < nums[mid]) right = mid - 1;
                else left = mid + 1;//(nums[mid]已被判断过)
            }
            else if(nums[left] > nums[mid]){//如果右半有序
                if(nums[mid]<target && target<=nums[right]) left = mid + 1;
                else right = mid - 1;//(nums[mid]已被判断过)
            }
        }
        return -1;
    }
};


int main(){
    vector<int> nums = {4,5,6,7,0,1,2};
    Solution solution;
    solution.search(nums, 3);
}